package com.lzq.leetcode.hoot100;

public class s416 {

    public boolean canPartition(int[] nums) {
        int len = nums.length;
        int sum = 0, max = 0;
        for (int i=0; i<len; i++) {
            sum += nums[i];
            max = Math.max(max, nums[i]);
        }
        // 第一次验证
        int half = sum / 2;
        if (half * 2 != sum || max > half) {
            return false;
        }
        // 开始dp
        boolean[][] dp = new boolean[len][half + 1];

        for (int i=0; i<len; i++) {
            dp[i][0] = true;
        }

        for (int i=0; i<len; i++) {
            for (int j=1; j<=half; j++) {
                dp[i][j] = i-1 >= 0 && ((dp[i-1][j]) || (j-nums[i]>=0 && dp[i-1][j-nums[i]]));
            }
        }

        return dp[len-1][half];
    }

    public static void main(String[] args) {
        s416 s416 = new s416();
        System.out.println(s416.canPartition(new int[]{1, 5, 11, 5}));
    }
}
